package src.leetcode.backtrack.medium_0131;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class partition {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.partition("abbab"));
    }
}

class Solution {
    List<List<String>> res = new ArrayList<>();
    List<String> path = new ArrayList<>();
    List<Integer> part = new ArrayList<>();
    boolean [][]dp;
    String s;
    public List<List<String>> partition(String s) {
        this.s = s;
        int n = s.length();
        dp = new boolean[n][n];

        for (int i = 0; i < n; ++i) {
            Arrays.fill(dp[i], true);
        }

        for (int i = n - 1; i >= 0; i--){
            for (int j = i + 1; j < n; j++){
                dp[i][j] = (s.charAt(i) == s.charAt(j)) && dp[i + 1][j - 1];
            }
        }

        part.add(0);
        dfs();
        return res;
    }

    private void dfs() {
        int start = part.get(part.size() - 1);
        for(int i = start; i < s.length(); i++){
            if(dp[start][i]){
                part.add(i + 1);
                path.add(s.substring(start, i + 1));
                if(i + 1 == s.length()){
                    res.add(new ArrayList<>(path));
                }
                dfs();
                path.remove(path.size() - 1);
                part.remove(part.size() - 1);
            }
        }
    }

    private boolean isPalindrome(int start, int end){
        for(; start < end; start++, end--){
            if(s.charAt(start) != s.charAt(end)) {
                return false;
            }
        }
        return true;
    }
}